/**
 * 124. 二叉树中的最大路径和
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
 */

const { createTreeNode } = require('../../libs/public');

let max;

/**
 * @param {TreeNode} root
 * @return {number}
 */
function subSum(root) {
  if (!root) return 0;
  const leftContribute = subSum(root.left);
  const rightContribute = subSum(root.right);
  const sum = root.val + Math.max(leftContribute, 0) + Math.max(rightContribute, 0);
  if (sum > max) max = sum;
  return root.val + Math.max(leftContribute, rightContribute, 0);
}

/**
 * @param {TreeNode} root
 * @return {number}
 */
function maxPathSum(root) {
  max = -Infinity;
  subSum(root);
  return max;
}

console.log(maxPathSum(createTreeNode([1, 2, 3])) === 6);
console.log(maxPathSum(createTreeNode([-10, 9, 20, null, null, 15, 7])) === 42);
